This invention is directed to the design of integrated circuits, and particularly to performing timing analysis for use during integrated circuit design phases.
Timing analysis of an integrated circuit (IC) is performed during the design phase of the IC. More particularly, the circuit designer calculates the times of signal arrival and departure to identify a time delay along a given path in the circuit. The timing analysis is used by the designer to optimize the circuit, resulting in changes to the IC design and the netlist. This procedure is repeated numerous times during IC design causing changes in the netlist.
Timing analysis is performed using a timing graph, which is an oriented graph representing the signal flow. The nodes of the graph are all of the pins in the netlist. To perform timing analysis, the timing graph is traversed twice. In the first pass, graph is traversed from the start points and the worst signal arrival time is calculated at each pin. Similarly, in the second pass, graph is traversed backwards and the departure time (sometimes called the xe2x80x9crequiredxe2x80x9d time) is calculated. The departure time represents the required duration for propagation of a signal through the cell. For each pin, the sum of arrival and departure times represents the delay of the worst path going through the pin.
In almost every design, there are paths that the user wants to be disregarded from the timing analysis. These are called xe2x80x9cfalse pathsxe2x80x9d and are conveyed to the timing analysis engines by the designer or user through xe2x80x9ctiming constraintsxe2x80x9d. Identifying and removing false paths from consideration is a difficult problem for the circuit designer. Belkhale et al., in xe2x80x9cTiming Analysis with Known False Sub Graphsxe2x80x9d, Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD ""95), pp 736-740 (1995) suggest identifying portions of the timing graph (subgraphs) that correspond to the false paths. However, the Belkhale et al. technique requires complex computation of multiple arrival and multiple departure times at each node, with different arrival and departure times at a node distinguished based on a set attribute. The set attribute value gives the set of false subgraphs the signal has come through. The complexity of the Belkhale et al. approach expands as the process is repeated for changes in the netlist.
In accordance with the present invention, a timing graph contains one or more known false paths containing nodes of at least two sets selected from FROM, THROUGH and TO nodes. The false paths are processed to include both FROM and TO nodes. The processed false paths are transformed into equivalent sets of two logical false paths. True path intervals are constructed as logical subgraphs that do not describe any equivalent false path.
In some embodiments, the processing of the false paths include combining false paths having two identical sets of FROM, THROUGH and TO nodes, and normalizing the false paths to have both FROM and TO sets. More particularly, the timing graph is traversed backward from the THROUGH nodes for all false paths having only THROUGH and TO sets to insert FROM sets, and is traversed forward from the THROUGH nodes for all false paths having only FROM and THROUGH sets to insert TO sets.
In other embodiments the false paths are transformed into equivalent sets have either (i) disjoint FROM nodes, or (ii) identical sets of FROM nodes and disjoint TO nodes. More particularly, the false paths are transformed to have sets of either identical or disjoint FROM nodes. The false paths are sorted into groups having common FROM sets, and the false paths having identical FROM sets are transformed to have sets of either identical or disjoint TO nodes.
In preferred embodiments, the process is carried out by a computer under the control of a computer readable program embedded as code on a computer readable medium, such as a hard disk drive. The computer operates under control of the computer readable program code to carry out the process and define the timing of the timing graph.